package com.lun.medium;

import java.util.HashMap;
import java.util.Map;

import com.lun.util.BinaryTree.TreeNode;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	Map<Integer, Integer> inMap = new HashMap<>();
    	for(int i = 0; i < inorder.length; i++)
    		inMap.put(inorder[i], i);
    	
    	return buildTree(inorder, 0, inorder.length - 1, // 
    			postorder, 0, postorder.length - 1, inMap);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, //  
    		int[] postorder, int postStart, int postEnd, Map<Integer, Integer> inMap) {
    	
    	if(inStart > inEnd || postStart > postEnd) return null;
    	TreeNode parent = new TreeNode(postorder[postEnd]);
    	
    	int parentIndexInInorder = inMap.get(parent.val); 
    	int leftSubtreeNodeNum = parentIndexInInorder - inStart;
    	
    	parent.left = buildTree(inorder, inStart, parentIndexInInorder - 1, // 
    			postorder, postStart, postStart + leftSubtreeNodeNum - 1, inMap);
    	
    	parent.right = buildTree(inorder, parentIndexInInorder + 1, inEnd, // 
    			postorder, postStart + leftSubtreeNodeNum, postEnd - 1, inMap);
    	
    	return parent;
    }
}
